class Solution
{
public:
    double mincostToHireWorkers(vector<int> &quality, vector<int> &wage, int k)
    {
        int n = quality.size();
        vector<pair<double, int>> costPerformace(n);
        for (int i = 0; i < n; ++i)
        {
            costPerformace[i] = {1.0 * wage[i] / quality[i], i};
        }
        sort(costPerformace.begin(), costPerformace.end(), [](auto &p1, auto &p2)
             { return p1.first < p2.first; });

        priority_queue<int> higherQualities;

        double minCost = 1e10;
        double totalCost = 0.0;
        int totalQuality = 0.0;
        for (int i = 0; i < k - 1; ++i)
        {
            higherQualities.push(quality[costPerformace[i].second]);
            totalQuality += quality[costPerformace[i].second];
        }
        for (int i = k - 1; i < n; ++i)
        {
            totalQuality += quality[costPerformace[i].second];
            higherQualities.push(quality[costPerformace[i].second]);
            totalCost = costPerformace[i].first * totalQuality;
            minCost = min(minCost, totalCost);
            totalQuality -= higherQualities.top();
            higherQualities.pop();
        }
        return minCost;
    }
};